package month1;

import java.util.*;

public class LetterCombinations17_06 {
    public static void main(String[] args) {
        System.out.println(letterCombinations("234"));
    }

    static Map<Character, String> map = new HashMap<Character, String>() {
        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };

    /**
     * 简单回溯
     * @param digits
     * @return
     */
    static List<String> letterCombinations(String digits) {
        List<String> ret = new ArrayList<>();
        if (digits.length() < 1) return ret;
        traceback(digits, ret, "", 0);
        return ret;
    }

    static void traceback(String digits, List<String> ret, String tmp, int i) {
        if (i == digits.length()) {
            ret.add(tmp);
            return;
        }
        String letters = map.get(digits.charAt(i));
        for (int j = 0; j < letters.length(); ++j) {
            traceback(digits, ret, tmp + letters.charAt(j), i + 1);
        }
    }
}
